package com.zs.letcode.illustration_of_algorithm;

import java.util.HashSet;
import java.util.Set;

/**
 * 剑指 Offer 57. 和为 s 的两个数字
 * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
 * <p>
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[2,7] 或者 [7,2]
 * 示例 2：
 * <p>
 * 输入：nums = [10,26,30,31,47,60], target = 40
 * 输出：[10,30] 或者 [30,10]
 *
 * <p>
 * 限制：
 * <p>
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i]<= 10^6
 * 相关标签
 * 数组
 * 双指针
 * 二分查找
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5832fi/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/28 09:13
 */
public class Chapter60 {
    public static void main(String[] args) {

    }

    private class Solution {
        public int[] twoSum(int[] nums, int target) {
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                if (set.contains(num)) {
                    return new int[]{num, target - num};
                }
                set.add(target - num);
            }
            return new int[]{-1, -1};
        }

        public int[] twoSum1(int[] nums, int target) {
            int i = 0, j = nums.length - 1;
            while (i < j) {
                int mid = (i + j) / 2;
                if (mid > target) {
                    j = mid;
                    continue;
                }
                if (nums[i] + nums[j] > target) {
                    j--;
                } else if (nums[i] + nums[j] < target) {
                    i++;
                } else {
                    return new int[]{nums[i], nums[j]};
                }
            }
            return new int[]{-1, -1};
        }
    }
}
